package cn.edu.xjtu.daily.April.day_4_12;

import java.util.Scanner;

/**
 * @author Hydrion-QLz
 * @date 2022-04-12 0:06
 * @description https://www.luogu.com.cn/problem/P1827
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String inOrder = sc.next();
        String preOrder = sc.next();
        sc.close();

        // 构造整个树
        construct(preOrder, inOrder, 0, preOrder.length(), 0, inOrder.length());
    }

    /**
     * 构造当前范围内的子树,中序序列中的范围：[inOrderLeft, inOrderRight),前序序列中的范围：[preOrderLeft, preOrderRight)
     *
     * @param preOrder      前序遍历序列
     * @param inOrder       中序遍历序列
     * @param inOrderLeft   中序遍历序列的左边界，包含
     * @param inOrderRight  中序遍历序列的右边界，不包含
     * @param preOrderLeft  前序遍历的左边界，包含
     * @param preOrderRight 前序遍历的右边界，不包含
     */
    private static void construct(String preOrder, String inOrder, int inOrderLeft, int inOrderRight, int preOrderLeft, int preOrderRight) {
        if (inOrderLeft == inOrderRight) {
            // 当区间长度为0表示没有元素了
            return;
        }
        String inOrderSubStr = inOrder.substring(inOrderLeft, inOrderRight);//当前子树的所有结点的中序序列

        char rootCh = preOrder.charAt(preOrderLeft);// 当前子树根节点的字符
        int rootIdx = inOrderSubStr.indexOf(rootCh) + inOrderLeft;// 当前子树的根节点在中序序列中的下标
        int leftSubTreeLength = rootIdx - inOrderLeft;// 左子树长度

        // 构造左子树
        construct(preOrder, inOrder, inOrderLeft, rootIdx, preOrderLeft + 1, preOrderLeft + 1 + leftSubTreeLength);

        // 构造右子树
        construct(preOrder, inOrder, rootIdx + 1, inOrderRight, preOrderLeft + 1 + leftSubTreeLength, preOrderRight);

        System.out.print(rootCh);
    }
}
